package com.zlk.algorithm.algorithm.dynamicPlan.longestIncreasingSubsequence;

import com.zlk.algorithm.algorithm.dynamicPlan.twoDimension.RobotWalk;

import java.util.Arrays;

// 俄罗斯套娃信封问题
// 给你一个二维整数数组envelopes ，其中envelopes[i]=[wi, hi]
// 表示第 i 个信封的宽度和高度
// 当另一个信封的宽度和高度都比这个信封大的时候
// 这个信封就可以放进另一个信封里，如同俄罗斯套娃一样
// 请计算 最多能有多少个信封能组成一组“俄罗斯套娃”信封
// 即可以把一个信封放到另一个信封里面，注意不允许旋转信封
// 测试链接 : https://leetcode.cn/problems/russian-doll-envelopes/
public class Code02_RussianDollEnvelopes {


    //其问题就是最长递增子序列变体
    //先按照宽度从小到大排序，再按照高度从大到小排序（为啥要按照高度从大到小排序，避免套中相同宽度下的）
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes,(a,b)->a[0]!=b[0]?a[0]-b[0]:b[1]-a[1]);
        int length = envelopes.length;
        int[] ends = new int[length];
        int activeLen = 0;
        for (int i = 0; i < length; i++) {
            int index = findLeft(ends,activeLen,envelopes[i][1]);
            if(index!=-1){
                ends[index] = envelopes[i][1];
            }else{
                ends[activeLen++] = envelopes[i][1];
            }
        }
        return activeLen;
    }

    private int findLeft(int[] ends, int activeLen, int num) {
        int l = 0;
        int r = activeLen-1;
        int mid = 0;
        int ans = -1;
        while (l<=r){
            mid = (l+r)/2;
            if(ends[mid]>=num){
                ans = mid;
                r = mid-1;
            }else{
                l = mid+1;
            }
        }
        return ans;
    }
}
